
// 440.字典序的第K小数字
class Solution {
    typedef long long LL;
public:
    int findKthNumber(int n, int k) {
        // 使用多叉树进行模拟

        // 计算子节点总数
        function<int(int)> count_subtree_size = [&](int root)
        {
            LL left = root , right = root + 1;
            int ret = 0;
            while(left <= n)
            {
                ret += right - left;
                left *= 10;
                right = min(right*10 , (LL)n + 1);
            }
            return ret;
        };

        LL num = 1;
        k--;
        while(k > 0)
        {
            int sz = count_subtree_size(num);
            if(k >= sz)
            {
                num++;
                k -= sz;
            }
            else
            {
                num *= 10;
                k--;
            }
        }
        return num;
    }
};